package medium

func maxProfit(prices []int) int {
	if len(prices) == 0 {
		return 0
	}
	// dp0：当天结束后持有股票
	// dp1：不持有股票，本日卖出，下一天为冷冻期
	// dp2: 不持有股票，本日不卖出，下一天为非冷冻期
	// 第1天，有股票（dp0）则表示当天买入:-prices[0]
	// 第1天，无股票卖出，（则当天可以先买入后卖出）
	// 第1天，无股票不卖出，则为0(即不交易)
	dp0, dp1, dp2 := -prices[0], 0, 0
	for i := 1; i < len(prices); i++ {
		// 如果当前结束后仍持有股票，有两种情况：一种是该股票来源于前一天，一种是今天买入的（前一天结束后不能为冷冻期，否则今天无法买入）
		NewDp0 := Max(dp0, dp2-prices[i])
		// 如果当天结束后处于冷冻期，则说明当天卖出了股票，前一天结束后肯定持有股票（且前一天结束后不处于冷冻期）
		NewDp1 := Max(dp0+prices[i])
		// 如果当前结束后位于非冷冻期且不持有股票，有两种情况：一种是前一天结束后处于冷冻期（即今天是冷冻期），另一种是今天卖出
		NewDp2 := Max(dp1, dp2)
		dp0, dp1, dp2 = NewDp0, NewDp1, NewDp2
	}
	return Max(dp1, dp2)
}